package com.wdc.binarytree;

import java.util.Arrays;

@SuppressWarnings("all")
//leetcode 106  根据后序跟中序返回这颗二叉树
public class E03LeetCode106 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0){
            return null;
        }
        //根据后序可以得到根节点
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        //根据中序可以分割左右子树
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val){
                //找到索引为 i 找到左右子树
                int[] inLeft = Arrays.copyOfRange(inorder,0,i);
                int[] inRight = Arrays.copyOfRange(inorder,i + 1 ,inorder.length);
                //继续分割后序数组，方便后面递归
                int[] postLeft = Arrays.copyOfRange(postorder,0,i);
                int[] postRight = Arrays.copyOfRange(postorder,i,postorder.length-1);

                root.left=buildTree(inLeft,postLeft);
                root.right=buildTree(inRight,postRight);
                break;
            }
        }

        return root;
    }




}
